package alogrithm;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/18 20:36
 */
public class MaxInWindows {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1]);
        int n = num.length;
        for (int i = 0; i < size; ++i) {
            priorityQueue.offer(new int[]{num[i], i});

        }
        int[] ans = new int[n - size + 1];
        ans[0] = priorityQueue.poll()[0];
        for (int i = size; i < n; ++i) {
            priorityQueue.offer(new int[]{num[i], i});
            while (priorityQueue.peek()[1] <= i - size) {
                priorityQueue.poll();
            }
            ans[i - size + 1] = priorityQueue.peek()[0];
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i : ans) {
            res.add(i);
        }
        return res;

    }
}
